package 链表;

public class MyLinkedList {
    private Node head;
    private Node last;
    private int size;

    public MyLinkedList(){
        head = null;
        last = null;
        size = 0;
    }

    public boolean add(String e){
        Node node = new Node(e);
        if (head == null){
            head = last= node;
        }else {
            node.prev = last;
            last.next = node;
            last = node;
        }
        size++;
        return true;

    }

    public void add(int index, String e){
        if (index < 0 || index > size){
            throw new ArrayIndexOutOfBoundsException();
        }

        if (head == null){
            Node node = new Node(e);
            head = last = node;
        }else if (index == 0){
            Node node = new Node(e);
            node.next = head;
            head.prev = node;
            head = node;
        }else if (index == size){
            Node node = new Node(e);
            last.next = node;
            node.prev = last;
            last = node;
        }else {
            Node node = new Node(e);
            Node pre = head;
            for (int i = 0; i < index - 1; i++){
                pre = pre.next;
            }
            Node next = pre.next;
            pre.next = node;
            next.prev = pre;
            node.next = next;
            next.prev = node;
        }
        size++;
    }

    public String remove(int index){
        if (index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        String e;
        if (size == 1){
            e = head.val;
            head = last = null;
        }else if (index == 0){
            e = head.val;
            head = head.next;
            head.prev = null;
        }else if (index == size - 1){
            e = last.val;
            last = last.prev;
            last.next = null;
        }else {
            Node toDelete = head;
            for (int i = 0; i < index; i++){
                toDelete = toDelete.next;
            }
            e = toDelete.val;
            Node pre = toDelete.prev;
            Node next = toDelete.next;

            pre.next = next;
            next.prev = pre;
        }
        size--;
        return e;
    }

    boolean remove(String e){
        int i = indexOf(e);
        if (i < 0){
            return false;
        }
        remove(i);
        return true;
    }

    public String get(int index){
        if (index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        Node findNode = head;
        for (int i = 0; i < index; i++){
            findNode = findNode.next;
        }
        return findNode.val;
    }

    public String set(int index, String e){
        if (index < 0 || index >= size){
            throw new ArrayIndexOutOfBoundsException();
        }
        Node setNode = head;
        for (int i = 0; i < index; i++){
            setNode = setNode.next;
        }
        setNode.val = e;
        return e;
    }

    public boolean contains(String e){
        return indexOf(e) > 0;
    }

    public int indexOf(String e){
        int i = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.val.equals(e)){
                return i;
            }
            i++;
        }
        return -1;
    }

    public int lastIndexOf(String e){
        int i = size - 1;
        for (Node cur = last; cur != null; cur = cur.prev){
            if (cur.val.equals(e)){
                return i;
            }
            i--;
        }
        return -1;
    }

    public void clear(){
        head = last = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("[");
        Node cur = head;
        while (cur != null){
            stringBuilder.append(cur.val);
            if (cur.next  != null){
                stringBuilder.append(",");
            }
            cur = cur.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
